Взаимнопростая таблица - 2

Максимальная оценка за эту задачу — 40 баллов. Учитывается последняя посылка!

В этой задаче мультитест и другие ограничения (см. раздел «Входные данные»). Условие задачи и форматы ввода и вывода полностью совпадают с предыдущей задачей, однако в этой задаче вам необходимо сдать на проверку текстовый файл с ответом на конкретный тест, который вы должны сгенерировать на своем компьютере. Скачать файл со входными данными для этой задачи вы можете нажав на ссылку «Скачать условие задачи» внизу этой страницы (после раздела «Система оценивания»).

Во время тура ответ будет проверяться только на соответствие формату, проверка с выставлением баллов будет осуществляться после окончания тура. Статус OK и 0 баллов во время тура означает, что сданный вами файл соответствует формату и будет проверен после тура, в случае других статусов файл не соответствует формату и вам следует проверить и исправить его.

В клетки таблицы n × n n \times n необходимо расставить числа от 1 до n2 n^2 , каждое по одному разу. Расстановка тем лучше, чем меньше в ней плохих пар соседних клеток. Соседними считаются клетки, имеющие общую сторону. Пара соседних клеток считается плохой, если числа в этих клетках не являются взаимно простыми. Два числа называются взаимно простыми, если их наибольший общий делитель равен 1 1 .

Составьте таблицу с наименьшим количеством плохих пар клеток.

Формат ввода

В первой строке задается количество наборов входных данных T T . В этой задаче T T всегда равно 5.

В первой строке каждого описания набора входных данных дано одно целое число n n ( 2 ≤ n ≤ 1000 ) (2 \le n \le 1000) — размер таблицы.

Формат вывода

Для каждого набора входных данных выведите n n строк, в каждой из которых должно быть по n n целых чисел — выбранную таблицу.

Все числа от 1 1 до n2 n^2 должны встретиться в таблице ровно один раз.

Система оценивания

Оценка за эту задачу — 40 баллов.

В этой задаче 1 тест, оценивающийся максимум в 40 баллов. Оценка за тест вычисляется как средняя оценка по наборам входных данных в тесте, умноженная на максимальный балл за тест. В этой задаче в единственном тесте — 5 наборов входных данных. Оценка за набор входных данных вычисляется по формуле:

g r a d e = max ⁡ ( 1 − 1.7 ⋅ b a d n2 , 0 ) grade = \operatorname{max}(1 - 1.7\cdot \frac{bad}{n^2}, 0)

где b a d bad и n n — количество плохих пар и размер таблицы соответственно.